#include <stdio.h>

void PrintArray(int *a,int size)       //打印函数
{
    for(int i=0;i<size;i++)
    {
        printf(" %d",a[i]);

    }
    printf("\n");
}

void Swap(int *a,int *b)                //换位函数
{
    int temp=*a;
    *a=*b;
    *b=temp;
}

void BubbleSort(int *a,int size)        //冒泡排序
{
    for(int i=0;i<size-1;i++)   //将n个数归位
    {
        int flag = 0;
        for (int j=0;j<size-i-1;j++)  //两两比较
        {
            if(a[j]>a[j+1])
            {
                flag = 1;
                Swap(&a[j],&a[j+1]);
            }
        }
        if(flag == 0) //数列已经有序
        {
            break;      //跳出循环
        }
    }
}

void Insertsort(int *a,int size)         //插入排序
{
    for(int i=1;i<size;i++)
    {
        int j=i;    //这个位置是即将要插入的数
        int temp=a[j];
        for(;j>0;j--)
        {
            if(a[j-1]>temp)     //前面的数比我大
            {
                a[j]=a[j-1];    
            }
            else         //前面的数不比我大
            {
                break;
            }
        }
        a[j]=temp;
    }
}

void ChooseSort(int *a,int size)        //选择排序
{
    for(int i=0;i<size-1;i++)
    {
        int min = i;
        for(int j=i+1;j<size;j++)
        {
            if(a[min]>a[j])
            {
                min=j;
            }
        }
        Swap(&a[min],&a[i]);
    }
}

void ChooseSort2(int *a,int size)       //双指针选择排序算法
{
    int left=0;
    int right=size-1;
    while(left<right)
    {
        int min = left;
        int max = right;
        for(int i = left;i<=right;i++)
        {
            if(a[i]<a[min])
                min = i;
            if(a[i]>a[max])
                max=i;
        }
        Swap(&a[left],&a[min]);     //极值在两端
        if(max == left)
        {
            max = min;
        }
        Swap(&a[right],&a[max]);       
        left++;
        right--;
    }
}   

void FastSort(int*a ,int start,int end)     //快速排序      双指针  递归  分治
{
    if(start >= end)    //终止条件
    return;
    int left=start;
    int right=end;
    int temp=a[start];
    while(left<right)
    {
        //从右往左找比基准值小的
        while(a[right]>temp && left < right)
            right--;
        if(left <right)
        
            a[left++]=a[right]; //把比基准值小的数放到左边

        //从左往右找比基准值大的
        while(a[left] < temp && left < right)
            left++;
        if(left < right)
            a[right--] = a[left];//把比基准值大的数放右边
    }
    a[left] = temp;

    FastSort(a,start,left - 1);
    FastSort(a,right+1,end);
}

int BinarySearch(int *a,int size,int element)   //二分排序
{
    int left =0;
    int right = size-1;
    while(left<=right)
    {
        int mid = left +(right-left)/2;
        //(left & right)+((left ^ right)>>1);
        if( a[mid] == element)
        {
            return mid;
        }
        else if(a[mid]>element)
        {
            right=mid-1;
        }
        else if(a[mid]<element)
        {
            left=mid+1;
        }
    }
    return -1;
}

int main()
{
    int a[]={3,65,1,46,24};
    PrintArray(a,sizeof(a)/sizeof (a[0])); 
    //Insertsort(a,5);        //插入排序
    //BubbleSort(a,5);      //冒泡排序
    //ChooseSort(a,5);        //选择排序
    //ChooseSort2(a,sizeof(a)/sizeof (a[0])); //双指针选择排序算法
    //FastSort(a,0,sizeof(a)/sizeof(a[0])-1);

    int index=BinarySearch(a,sizeof(a)/ sizeof(a[0]),46);
    if(index == -1)
    {
        printf("没找到！\n");
    }
    else
    {
        printf("找到了，在%d位置\n",index);
    }

    PrintArray(a,sizeof(a)/sizeof (a[0])); 
    return 0;
}